#include "Mat_Chain_Mul_Calculator.h"

/**
 * @brief 初始化一个矩阵链乘法计算器
 * @param p 传入的矩阵尺寸数组指针，如果有n个矩阵链乘， 大小应为n+1
 */
Mat_Chain_Mul_Calculator :: Mat_Chain_Mul_Calculator(vector<int>* p)
{
    this->mat_chain_ptr = p;
    int length = p->size() - 1;
    //初始化m和s
    for (int i = 0; i < length + 1; i++)
    {
        vector<long int > row;
        for (int j=0; j<length + 1; j++){
            row.push_back(0);
        }
        m.push_back(row);
        s.push_back(row);
    }
}

/**
 * @brief 使用动态规划法计算矩阵链乘的最优解
 * @note 没有返回值和参数，从类的mat_chain_ptr中取值，计算结果存入m和s。
 */
void Mat_Chain_Mul_Calculator :: Matrix_Chain_Order(){
    int n = this->mat_chain_ptr->size() - 1;
    for (int l = 2; l <= n; l++)     //l is the chain length
    {
        for (int i = 1; i <= n - l + 1; i++)
        {
            int j = i + l - 1;
            m[i][j] = 9223372036854775807;
            for (int k = i; k <= j - 1; k++)
            {
                long int q = m[i][k] + m[k+1][j] + (long)(*this->mat_chain_ptr)[i - 1] * (long)(*this->mat_chain_ptr)[k] * (long)(*this->mat_chain_ptr)[j];
                if(q < m[i][j]){
                    m[i][j] = q;
                    
                    s[i][j] = k;
                }
            }
        }
    }
}

/**
 * @brief 打印矩阵链乘的最优括号化方案
 * @param i 打印括号化方案的最左侧矩阵下标
 * @param j 打印括号化方案的最右侧矩阵下标
 */
void Mat_Chain_Mul_Calculator :: Print_Optimal_Parens(int i, int j){
    if(i == j){
        cout << "A_" << i;
    }
    else{
        cout << "(";
        Print_Optimal_Parens(i, s[i][j]);
        Print_Optimal_Parens(s[i][j]+1, j);
        cout << ")";
    }
}

/**
 * @brief 运行矩阵链乘计算器并打印结果和运算时间
 */
void Mat_Chain_Mul_Calculator :: run(){
    time_t begin, end;

    begin = clock();
    for (size_t i = 0; i < 1000000; i++)
    {
        this->Matrix_Chain_Order();
    }
    this->Print_Optimal_Parens(1, this->mat_chain_ptr->size()-1);
    cout << endl;
    end = clock();
    cout << "mul times = " << this->m[1][this->mat_chain_ptr->size()-1] << endl;
    cout << "time = " << double(end - begin) / CLOCKS_PER_SEC << endl << endl;
}

/**
 * @brief 打印m表和s表
 */
void Mat_Chain_Mul_Calculator::print_ms(){
    cout << "m表：" << endl;
    for (size_t i = 1; i < m.size(); i++)
    {
        for (size_t j = 1; j < m[0].size(); j++)
        {
            printf("%20ld\t", m[i][j]);
        }
        cout << endl;
    }
    cout << "s表：" << endl;
    for (size_t i = 1; i < s.size(); i++)
    {
        for (size_t j = 1; j < s[0].size(); j++)
        {
            printf("%4ld\t", s[i][j]);
        }
        cout << endl;
    }
}